package ljl.alg.wangzheng_camp.round1.dp;

public class _53_max_sub_arr {
    
    public int maxSubArray(int[] nums) {
        int pre = 0, max = nums[0];
        for (int num : nums) {
            pre = Math.max(pre + num, num);
            max = Math.max(max, pre);
        }
        return max;
    }
    
    public int maxSubArray3(int[] nums) {
        class Tree {
            int sum, lsum, rsum, msum;
            private Tree(int sum, int lsum, int rsum, int msum) {
                this.sum = sum; this.lsum = lsum; this.rsum = rsum; this.msum = msum;
            }
            Tree(){}
            Tree init(int[] nums, int from, int to) {
                if (from == to) return new Tree(nums[from], nums[from], nums[from], nums[from]);
                int mid = (from + to) >>> 1;
                Tree left = init(nums, from, mid);
                Tree right = init(nums, mid + 1, to);
                sum = left.sum + right.sum;
                lsum = Math.max(left.lsum, left.sum + right.lsum);
                rsum = Math.max(right.rsum, left.rsum + right.sum);
                msum = Math.max(left.msum, Math.max(right.msum, left.rsum + right.lsum));
                return new Tree(sum, lsum, rsum, msum);
            }
        }
        return new Tree().init(nums, 0, nums.length - 1).msum;
    }
    
}
